package algorithm.middle;

import java.security.SignedObject;

/**
 * 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
 *
 * 一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
 *
 * 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-enclaves
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NumEnclaves1020 {

    int[][] sign;

    public int numEnclaves(int[][] grid) {
        int row =  grid.length;
        int line = grid[0].length;
        sign = new int[grid.length][grid[0].length];
        for (int i=0;i<line;i++){
            //第一行
            dfs(grid,0,i);
            //最后一行
            dfs(grid,row-1,i);
        }
        for (int j=1;j<row-1;j++){
            //第一列
            dfs(grid,j,0);
            //最后一列
            dfs(grid,j,line-1);
        }
        int res = 0;
        for (int i=0;i<row;i++){
            for (int j=0;j<line;j++){
                if (grid[i][j]==1 && sign[i][j]==0){
                    res++;
                }

            }
        }
        return res;
    }

    public void dfs(int[][] grid,int x,int y){
        //如果当前点已经被标注过，不需再遍历，返回
        //如果该点是海洋，则返回
        if (sign[x][y]==1 || grid[x][y]==0) return;
        sign[x][y]=1;
        //左
        if (y-1>=0){
            dfs(grid,x,y-1);
        }
        //下
        if (x+1<grid.length){
            dfs(grid,x+1,y);
        }
        //右
        if (y+1<grid[0].length){
            dfs(grid,x,y+1);
        }
        //上
        if (x-1>=0){
            dfs(grid,x-1,y);
        }
    }
}
